perm filename WINGED[00,BGB]1 blob
sn#097086 filedate 1974-04-17 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00008 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 2.0 THE WINGED EDGE POLYHEDRON REPRESENTATION.
C00005 00003 2.1 Winged Edge Link Fields.
C00010 00004
C00013 00005 2.2 Perimeter Accessing.
C00017 00006 2.3 Edge and Face Splitting.
C00019 00007
C00021 00008 2.4 Basic Polyhedron Synthesis.
C00023 ENDMK
C⊗;
2.0 THE WINGED EDGE POLYHEDRON REPRESENTATION.
2.1 Winged Edge Link Fields.
2.2 Perimeter Accessing.
2.3 Edge and Face Splitting.
2.4 Basic Polyhedron Synthesis.
2.0 Introduction.
In this chapter, a particular computer representation for
polyhedra is presented and some of its virtues are explained. The
data structures have been implemented as small blocks of words
containing pointers and data in the fashion usual to graphics and
simulation; an introduction to this technology can be found in Knuth
(Art of Programming, chapter 2, volume I).
Quickly reviewing Knuth's notation and terminolgy: a node is
a group of consecutive words of memory, a field is a named portion of
a node, a link is the absolute machine address of a node and the
notation for referring to a field of a node consists simply of the
field name followed by a link expression enclosed in parentheses. For
example the two faces of an edge node, whoes link is stored in the
variable EDGE, are found in the fields named NFACE and PFACE, and are
referred to as NFACE(EDGE) and PFACE(EDGE).
Although the latest language of implementation is PDP-10
machine code, earlier versions were coded in LISP and Stanford ALGOL
(SAIL with LEAP). However, examples of programs will be given in a
programming language which is like an ALGOL with node/link
syntax added.
2.1 Winged Edge Link Fields.
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. Each face
and each vertex points at one of the edges on its perimeter. Each
edge points at its two faces and its two vertices. Completing the
structure, each edge node contains a link to each of its four
immediate neighboring edges clockwise and counter clockwise around
face perimeters (as seen from the exterior side of the surface of the
polyhedron). These last four links are the wings of the edge, which
provide the basis for efficient face and vertex perimeter accessing.
Finally, the links of the edge nodes can be consistently oriented
with respect to the surface of the polyhedron so that the surface
always has two sides: the inside and the outside.
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. Thus the least number of different
link field names that need to be coined is ten; if we allow a link
name such as PED to serve different roles depending on whether it
applies to a body, face, edge or vertex. The data structures and the
link fields comprising the structures are listed in table (**) below.
The ten links names include: NFACE and PFACE for two fields that
contain face links in edges and the face ring, NED and PED for two
fields that contain edge links, NVT and PVT for two fields that
contain vertex links, and NCW, PCW, NCCW and PCCW for the four fields
that contain edge links and are called the wings.
---------------------------------------------------------------------
TABLE Data Structure Link Names
1. Face Ring of a Body. NFACE PACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW
NCCW PCCW
---------------------------------------------------------------------
As mentioned, advantages can be realized by constraining the
links of edge nodes to indicate a surface orientataion (interior and
exterior) and a linear orientation (directed vector). Since there are
four possible ways to put a pair of faces and a pair of vertices into
a pair of face fields and a pair of vertex fields; both surface and
linear orientation can be encoded. Viewing an edge of an existing
polyhedron (from the exterior side of its surface), the links are
arranged as illustrated in the figure (**). Appropriate subroutines
for creating, maintaining and exploiting edge orientation are
explained in later sections. Notice that although the vertices in the
figure are shown with only three edges, vertices may in fact have any
number of edges. The other potential edges would not be directly
connected to the middle edge of the figure and so were not shown.
FIGURE - THE WINGED EDGE.
(As viewed from the exterior of a solid).
\ /
NCCW(E) \ / PCW(E)
\ /
\ /
\ /
⊗ PVT(E)
|
|
NFACE(E) | E PFACE(E)
|
|
NVT(E) ⊗
/ \
/ \
/ \
NCW(E) / \ PCCW(E)
/ \
Next, it is necessary to mention some of the data fields. The
3-D coordinates of each vertex are kept in fields named XWC, YWC and
ZWC; the "WC" standing for "world coordinates". The 3-D perspective
projected coordinates of each vertex with respect to one camera at a
time are kept in fields named XPP, YPP, ZPP of vertex nodes.
2.2 Perimeter Accessing.
Given one edge of a face or vertex perimeter, the next edge
clockwise or counter clockwise from the given edge about the
particular face or vertex can be retrieved from the data structure
with the assistance of two subroutines called ECW and ECCW. The idea
of the edge clocking routines is to match the given face or vertex
with one of the faces and vertices of the given edge and to then
return the appropriate wing. One possible coding of ECCW and ECW might
be as follows:
COMMENT FETCH EDGE COUNTER CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
IF PFACE(E)=FV THEN RETURN(PCCW(E));
IF NFACE(E)=FV THEN RETURN(NCCW(E));
IF PVT(E)=FV THEN RETURN(PCW(E));
IF NVT(E)=FV THEN RETURN(NCW(E));
FATAL;
END "ECCW";
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
IF PFACE(E)=FV THEN RETURN(PCW(E));
IF NFACE(E)=FV THEN RETURN(NCW(E));
IF PVT(E)=FV THEN RETURN(NCCW(E));
IF NVT(E)=FV THEN RETURN(PCCW(E));
FATAL;
END "ECW";
The first edge of a face or vertex is (of course) directly
available from the PED field of the face or vertex. For example, the
code fragment below can be used to visit all the edges of a face.
COMMENT APPLY A FUNTION TO ALL THE EDGES OF A FACE;
INTEGER F,E,E0;
E←E0←PED(F);
DO FUNCTION(E) UNTIL E0=(E←ECCW(E,F));
Following the same idea as the edge clocking routines, a new
face or vertex can be retrieved relative to a given edge and a given
face or vertex. These routines include: FCW and FCCW which return the
face clockwise or counter clockwise from a given edge with respect to
a given vertex; VCW and VCCW which return the vetex clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which return the face or vertex of the given edge opposite the
given face or vertex. Together the seven routines: ECW, ECCW, VCW,
VCCW, FCW, FCCW and OTHER exhaust the possible oriented retrievals
from an edge node; they also alleviate the need to any explicit
reference a wing field when traveling the surface of a polyhedron.
2.3 Edge and Face Splitting.
Another simple virture of the winged edge representation is
that edges and faces can be split using subroutines involving only
local alterations to the data structure. Likewise, the splits can
be easily removed, in fact the main reason for doubly linked rings is
for the sake of rapid deletion of nodes. The edge split routine,
ESPLIT, makes a new edge and a new vertex and places them into the
surface topology as shown in figure (**). The kill edge-vertex
routine, KLEV, undoes an ESPLIT. The face split routine, MKFE,
creates a new edge and a new face and places them into the surface
topology as shown in figure (**); the kill face-edge routine, KLFE,
undoes a MKFE.
---------------------------------------------------------------------
FIGURES FOR ESPLIT & MKFE.
VNEW ← ESPLIT(E); E ← KLEV(VNEW);
ENEW ← MKFE(V1,F,V2); F ← KLFE(ENEW);
INTEGER PROCEDURE ESPLIT (INTEGER E);
BEGIN "ESPLIT"
INTEGER VNEW,ENEW,
COMMENT CREATE A NEW EDGE AND VERTEX ON THE BODY;
B ← BGET(E);
VNEW ← MKV(B);
ENEW ← MKE(B);
COMMENT CONNECT VERTICES AND FACES TO EDGES;
PVT(ENEW) ← PVT(E);
NVT(ENEW) ← VNEW;
PVT(E) ← VNEW;
PFACE(ENEW) ← PFACE(E);
NFACE(ENEW) ← NFACE(E);
COMMENT CONNECT EDGES TO VERTICES;
IF PED(V)=E THEN PED(V)←ENEW;
PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
NCW(ENEW) ← E; PCCW(ENEW) ← E;
PCW(E) ← ENEW; PCCW(E) ← ENEW;
WING(NCCW(E),ENEW);
WING(PCW(E),ENEW);
RETURN(VNEW);
END "ESPLIT";
2.4 Basic Polyhedron Synthesis.
In its most general form, the problem of synthesizing polyhedra
encompasses descriptive computer vision in that an advanced modeling program
should be able to make a polyhedral description of an object merely by looking
at it with a television camera. However, in this section I will consider
the environment internal to a geometric modeling system where
some of the geometry and topology of the desired polyhedron is available
and a winged edge model is desired.
In the ususal run of geometric routines and I/O formats the
First, get the proper kinds of nodes into the body rings.
Second, get the vertices correctly located (XWC,YWC,ZWC).
Third, to get each vertex and face pointed at one of its edges (PED fields).
Fouth, to get each edge pointed at its two faces and two vertices.
Finally, to get the wings of edges in place.
Clearly, the data structure given in section 2.1 is
redundant, consider for a moment which of the nodes and links can be
computed from the others.
For example the wing pointers can be restored
from the face-vertex pointers.
all the edges of a polyhedron could be compare
N*(N-1)/2 comparisons